1. Field of the Invention
The present invention generally relates to programmable finite state machines, and more specifically to a system and method of arranging multiple parallel programmable finite state machines using a shared transition table for finite state machine storage.
2. Description of the Related Art
Digital designs are typically partitioned into a data flow component and a control component. The control component is implemented using a set of finite state machines. Finite state machines are sequential in nature and progress from an initial state through a series of states in order to fulfill a certain task. The data flow component returns decision signals to the control component. Then, based on the decision signals returned from the data component, the control component decides the further steps that should be taken.
FIG. 1 illustrates a structure of a conventional finite state machine, including a core finite state machine logic area 1, a current state register 2 containing a current state, and an input register 3 containing an input vector. The core finite state machine logic area 1 calculates the next state 4 and the output 5.
FIG. 2 illustrates a conventional state transition table of a conventional finite state machine. A state transition table of a finite state machine specifies or defines the finite state machine. The current state, input vector, output vector, and next state are described by the state transition table illustrated in FIG. 2. The input vector (IV), output vector (OV), and next state (NS) describe the content of a single state transition element (STE). The values illustrated in FIG. 2 for IV and OV are representative of bit patterns. There are five transitions in the state transition table illustrated in FIG. 2. State S1 contains 3 STEs and State S2 contains 2 STEs.
FIG. 3 illustrates a conventional programmable finite state machine, which includes a finite state machine 31 and a storage 30. The storage 30 contains state machine transition information similar to the information illustrated in FIG. 2 and is used to program the finite state machine 31. The finite state machine 31 takes various inputs, including those emanating from the storage 30, and calculates the output vector to be output from the finite state machine core 31 and the next state to be output to the storage 30.
However, the conventional programmable finite state machine illustrated in FIG. 3 is not preferable due to the prohibitive cost of solely dedicating a storage unit to a programmable finite state machine. Since a semiconductor typically requires the implementation of multiple finite state machines, it would be advantageous for the implemented finite state machines to share storage units in order to optimize performance and cost.
FIG. 4 illustrates a conventional arrangement of multiple programmable finite state machines 41 utilizing a single multiport array storage unit 40. Multiple programmable finite state machines 41, up to an amount n, simultaneously make calls and access the single multiport array storage unit 40 for programming purposes.
FIG. 5 illustrates a conventional single programmable finite state machine including a state transition array (STA) 50. The STA 50 is organized such that each row contains all of the state machine transitions of a single state. In other words, one row of the STA 50 provides all of the STEs of a state. The state value in the current state register 2 is used as an index into the STA 50.
The programmable finite state machine 51 includes input vector match logic and output/next state select logic. The input vector match logic of the programmable finite state machine 51 compares all of the input vectors of the different STEs with the input comparators fed to the programmable finite state machine 51 and searches for an STE match. One of these comparators will have an STE match, which is represented by a comparator output of “1”. All other comparators will not have an STE match and are represented by the comparator output of “0”. The comparator that has the STE match controls the output/next state select logic.
When the STE match is found, the input vector match logic selects the matched STE and outputs the result to the output/next state select logic. Then, the output/next state select logic selects the comparator output of “1”. The output/next state select logic then drives the output vector value of the selected STE to the data flow output and the next state value 4 of the selected STE to the current state register 2 as control input.
When multiple programmable finite state machines are sharing a single multiport array storage unit, the single multiport array storage unit must have an equal amount of ports to the number of programmable finite state machines. However, due to the large amount of programmable finite state machines required in a single application, this conventional arrangement is no longer practical due to the number of ports that necessarily must equal the amount of programmable finite state machines. Multiport arrays typically are less than preferable if referenced by a number of programmable finite state machines exceeding three or four.
Thus, it is desirable not only for individual finite state machines to be programmable, but also for different applications executed on the same finite state machines to share the same transition table. It is also desirable for an STA to be much larger than the conventional STA.